package jp.sourceforge.talisman.mds.cluster;

/*
 * $Id: LanceWilliamsClusteringMethod.java,v 1.1 2009/09/12 05:06:01 weiwei Exp $
 */

import jp.sourceforge.talisman.mds.Item;
import jp.sourceforge.talisman.mds.Table;
import jp.sourceforge.talisman.mds.distance.ClusterDistanceCalculator;

/**
 * This is an implementation of LW method.
 * This method uses updating distance such as:
 * d_{(IJ)K} = \alpha_I d_{IK} + \alpha_J d_{JK} + \beta d_{IJ} + \gamma | d_{IK} - d_{JK} |
 * 
 * @author Haruaki Tamada
 * @version $Revision: 1.1 $ 
 */
class LanceWilliamsClusteringMethod extends AbstractClusteringMethod{
    public LanceWilliamsClusteringMethod(ClusteringParameter param) throws ParameterTypeMismatchException{
        super(param);
        if(!(param instanceof HierarchicalClusteringParameter)){
            throw new ParameterTypeMismatchException("HierarchicalClusteringParameter is required");
        }
    }

    public LanceWilliamsClusteringMethod(HierarchicalClusteringParameter param){
        super(param);
    }

    @Override
    protected Cluster[] doClustering(Item[] items, ClusteringParameter parameter){
        HierarchicalClusteringParameter param = (HierarchicalClusteringParameter)parameter;
        Cluster[] clusters = initClusters(items, param);
        ClusterDistanceCalculator cdc = param.getClusterDistanceCalculator();
        Table<Cluster> table = new Table<Cluster>();
        for(int i = 0; i < clusters.length; i++){
            for(int j = 0; j < i; j++){
                table.addValue(clusters[i], clusters[j], cdc.calculate(clusters[i], clusters[j]));
            }
        }

        while(table.getKeySize() > param.getNumberOfCluster()){
            Cluster clusterI = null, clusterJ = null;
            double distance = Double.MAX_VALUE;
            
            for(Table.Entry<Cluster> entry: table){
                Number value = entry.getValue();
                if(value != null && value.doubleValue() < distance){
                    clusterI = entry.getX();
                    clusterJ = entry.getY();
                    distance = entry.getValue().doubleValue();
                }
            }

            if(clusterI != null && clusterJ != null){
                Cluster clusterIJ = new Cluster();
                clusterIJ.setName(clusterI.getName() + ", " + clusterJ.getName());
                for(Item item: clusterI) clusterIJ.addItem(item);
                for(Item item: clusterJ) clusterIJ.addItem(item);

                for(Cluster clusterK: table.getKeySet()){
                    if(clusterK != clusterI && clusterK != clusterJ){
                        table.addValue(clusterIJ, clusterK,
                            cdc.update(clusterI, clusterJ, clusterK, 
                                table.getValue(clusterI, clusterJ).doubleValue(),
                                table.getValue(clusterI, clusterK).doubleValue(),
                                table.getValue(clusterJ, clusterK).doubleValue()
                            )
                        );
                    }
                }
                table.removeRow(clusterI);
                table.removeRow(clusterJ);
                table.removeColumn(clusterI);
                table.removeColumn(clusterJ);
            }
        }

        return table.getKeys(new Cluster[table.getKeySize()]);
    }

    private Cluster[] initClusters(Item[] items, HierarchicalClusteringParameter param){
        Cluster[] clusters = new Cluster[items.length];

        for(int i = 0; i < items.length; i++){
            clusters[i] = new Cluster();
            clusters[i].setName(items[i].getName());
            clusters[i].addItem(items[i]);
        }
        return clusters;
    }
}
